package leetcode_800;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 *@author 周杨
 *ReorganizeString_767 给定一个字符串 问能否重组这个字符串 使得所有字符不相邻排列 如果不能 返回空字符串
 *describe:双向铺 首先确定最多字符 然后i+=2 间隔铺 之后的也如此铺 只是要注意会转一次头 AC 85%
 *2018年10月19日 下午12:09:07
 */
public class ReorganizeString_767_ {
	public String reorganizeString(String S) {
        int []map=new int[26];
        char []chars=S.toCharArray();
        int max=0;
        char maxChar='a';
        for(int i=0;i<chars.length;++i) {
        	map[chars[i]-'a']++;
        	if(max<map[chars[i]-'a']) {
        		max=map[chars[i]-'a'];
        		maxChar=chars[i];
        	}
        }
        if(max>(S.length()+1)/2)//超过了一半的数目 那么怎么都放不下
        	return "";
        int index=0;
        while(map[maxChar-'a']>0) {//将最多字符铺满
        	chars[index]=maxChar;
            map[maxChar-'a']--;
        	index+=2;
        }
        for(int i=0;i<26;++i) {
        	while(map[i]>0) {
        		if(index>=S.length())//转头再铺
            		index=1;
        		chars[index]=(char) ('a'+i);
        		--map[i];
        		index+=2;
        	}
        }
        return new String(chars);
    }
	
	/**
	 * describe:统一接口 排列整个数组 使每个元素差距至少K 用优先队列
	 * 2018年10月19日 下午12:14:33
	 */
	public String reorganizeString2(String S) {
        if (S == null || S.length() == 0) {
            return "";
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char c : S.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));
        pq.addAll(map.entrySet());
        StringBuilder sb = new StringBuilder();
        Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
        while (!pq.isEmpty()) {
            Map.Entry<Character, Integer> entry = pq.poll();
            sb.append(entry.getKey());
            entry.setValue(entry.getValue() - 1);
            queue.offer(entry);
            while (queue.size() > 1) {
                Map.Entry<Character, Integer> temp = queue.poll();
                if (temp.getValue() > 0) {
                    pq.offer(temp);//重新排进去
                }
            }
        }
        return sb.length() == S.length() ? sb.toString() : "";
    }
	
	
	/**
	 * describe:存放顺序错误 因为vvvlo这样用例不能过
	 * 2018年10月19日 上午11:12:14
	 */
	public String reorganizeString1(String S) {
        int []map=new int[26];
        char []chars=S.toCharArray();
        int max=0;
        for(int i=0;i<chars.length;++i) {
        	map[chars[i]-'a']++;
        	max=Math.max(max, map[chars[i]-'a']);
        }
        if(max>(S.length()+1)/2)//超过了一半的数目 那么怎么都放不下
        	return "";
        int index=0;
        while(index<S.length()) {
        	for(int i=0;i<26;++i) {
        		if(map[i]>0) {
        			chars[index++]=(char) (i+'a');
        			--map[i];
        		}
        	}
        }
        return new String(chars);
    }
}
